package com.leetcode.array_matrix;


import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/7/22 22:28
 */
public class KthSmallest_378 {

    static class Node {
        int value, index, cursor;

        public Node(int value, int index, int cursor) {
            this.value = value;
            this.index = index;
            this.cursor = cursor;
        }
    }

    public int kthSmallest(int[][] matrix, int k) {
        Queue<Node> queue = new PriorityQueue<>(k, Comparator.comparingInt(o -> o.value));

        for (int i = 0; i < matrix.length; i++) {
            Node node = new Node(matrix[i][0], i, 0);
            queue.offer(node);
        }

        while (k-- > 1) {
            Node node = queue.poll();
            if (node.cursor == matrix[node.index].length - 1)
                continue;
            node.cursor++;
            node.value = matrix[node.index][node.cursor];
            queue.offer(node);
        }

        return queue.peek().value;
    }

}
